The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
In this paper, we deal with the problem of mapping data structures, called hosts, into as few distinct memory modules as possible to guarantee that sets of distinct host nodes, called templates, can be accessed in parallel and without memory conflicts. An efficient solution to this important problem leads to a higher memory bandwidth and a better overall performance of a multiprocessor system. ...
In this paper we study the packet routing problem under the matching model proposed by Alon, Chung and Graham [1]. We extend the model to allow more than one packet per origin and destination node. We give tight bounds for the many-to-one routing number for complete graphs, complete bipartite graphs and linear arrays. We also present an efficient algorithm for many-to-one routing on an trees (and...
Routing schemes often rely on local tables that associate with each destination node v a parent link on which to forward messages to v. The set of parent links form a directed tree to v. Such tables suffer from the fact that they do not provide a full representation of the entire network, and therefore are vulnerable to dynamic network changes and cannot tolerate faults. In this paper we propose a...
Heilbronn conjectured that given arbitrary n points from R 2, located in the unit square (or disc), there must be three points which form a triangle of area at most O(1/n2). This conjecture was shown to be false by a nonconstructive argument of Komlós, Pintz and Szemerédi [6] who showed that for every n there is a configuration of n points in the unit square where all triangles have area at least...
A polygonal curve can be described using different levels of resolutions (multiresolution). Progressive transmission allows a coarse rendition of a polygonal curve to be sent first to give the receiver an early impression of content (low-level resolution); then subsequent transmission provides progressively finer details (high-level resolution). In this paper, a novel polygonal curve approximation...
Let S be a set of n points in the plane and CH(S) be the convex hull of S. An ε-strongly convex δ-superhull is a polygon P satisfying the following conditions: (1) P has at most O(n) vertices, (2) P contains all the points of S, (3) no vertex of P lies farther than δ outside CH(S), and (4) P is convex and remains convex even if its vertices are perturbed by as much as ε (when ε = δ = 0, P is equal...
This paper studies the idea of answering range searching queries using simple data structures. The only data structure we need is the Delaunay Triangulation of the n input points. We show that when the query polygons are well-shaped the expected query time is O(n1/3 + Q + n ⁗ area(Q)), where Q is the size of the query polygon Q and n ⁗ area(Q) is the expected number of output points, which...
We resolve a conjecture of Hartmanis from 1978 about sparse hard sets for nondeterministic logspace (NL). We show that there exists a sparse hard set S for NL under logspace many-one reductions if and only if NL = L (deterministic logspace).
For ordinary circuits with a fixed upper bound on the maximal fanin of gates it has been shown that logarithmic redundancy is necessary and sufficient to overcome random hardware faults. Here, we consider the same question for unbounded fanin circuits that in the noise-less case can compute Boolean functions in sublogarithmic depth. Now the details of the fault model become more important. ...
Let S be a set of n elements, and let H be a set-system on S, which satisfies that the size of any element of H is divisible by m but the intersection of any two elements of H is not divisible by m If m is a prime or prime-power, then the famous Frankl-Wilson theorem [3] implies that |H| = O(nm-1), i.e. for fixed m, its size is at most polynomial in n. This theorem has numerous applications...
An ordered binary decision diagram (OBDD) is a graph representation of a Boolean function, and it is considered as a restricted branching program. According to its good properties, an OBDD is widely used in computer aided logic design. In this paper, the size of ordered binary decision diagrams representing threshold functions is discussed. First, we prove an Ω(n2cn1-ε) lower bound on...
Biologists have hotly debated the merits of various algorithms for phylogenetic reconstruction for many years. In this paper, we analyze the performance of the popular neighbor-joining algorithm. In particular, we determine the L∞ radius under which the method will determine the correct tree topology. In fact, this radius is optimal for all distance-based methods, the class of methods which...
We consider the problem of inferring the evolutionary tree of a set of n species. We propose a quartet reconstruction method which specifically produces trees whose edges have strong combinatorial evidence. For this purpose we use the Q* relation [3], defined as the maximum subset of resolved quartets which is equivalent to a tree. We further investigate the properties of this variation of the NP-hard...
The estimation of evolutionary history from biomolecular sequences is a major intellectual project in systematic biology and many methods are used to reconstruct phylogenetic (i.e. evolutionary) trees from sequence data. In this paper, we report on an extensive performance analysis of parsimony and two distance-based methods, a popular method called neighbor joining, and a new method developed by...
In this paper we study a few important tree optimization problems with applications to computational biology. These problems ask for trees that are consistent with an as large part, of the given data as possible. We show that the maximum homeomorphic agreement subtree problem cannot be approximated within a factor of Nε, where N is the input size, for any 0 ≤ ε < 1/18 in polynomial time unless...
In Computable Analysis each computable function is continuous and computably invariant, i.e. it maps computable points to computable points. On the other hand, discontinuity is a sufficient condition for non-computability, but a discontinuous function might still be computably invariant. We investigate algebraic conditions which guarantee that a discontinuous function is sufficiently discontinuous...
This paper deals with the computability of sequences of reals and sequences of functions within the framework of Grzegorczyk's hierarchy, which is in the Number 1 of the addendum to open problems in [4]. We combine the two concepts, computability of sequences of real valued functions and Grzegorczyk's hierarchy of recursive number theoretic functions, together, and examine the computability on real...
In this paper we extend computability theory to the spaces of continuous, upper and lower semi-continuous real functions. We apply the framework of TTE, Type-2 Theory of Effectivity, where not only computable objects but also computable functions on the spaces can be considered. First some basic facts about TTE are summarized. For each of the function spaces, we introduce several natural representations...
Visual cryptography and (k, n)-visual secret sharing schemes were introduced by Naor and Shamir in [NaSh1]. A sender wishing to transmit a secret message distributes n transparencies among n recipients, where the transparencies contain seemingly random pictures. A (k, n)-scheme achieves the following situation: If any k recipients stack their transparencies together, then a secret message is revealed...
We propose a new Rabin-type scheme, based on y2 ≡ x3 + bx2 mod n, that extends a scheme proposed by Meyer and Müller based on elliptic curves. The new scheme has security also equivalent to factorisation of n, seems easier in implementation and does not depend on probabilistic algorithms.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.